今天我们看一道 [leetcode](https://leetcode.cn/problems/count-array-pairs-divisible-by-k/description/) hard 难度题目：统计可以被 K 整除的下标对数目。

## 题目

给你一个下标从 0 开始、长度为 `n` 的整数数组 `nums` 和一个整数 `k` ，返回满足下述条件的下标对 `(i, j)` 的数目：

- `0 <= i < j <= n - 1` 且
- `nums[i] * nums[j]` 能被 k 整除。
 
**示例 1：**

```
输入：nums = [1,2,3,4,5], k = 2
输出：7
解释：
共有 7 对下标的对应积可以被 2 整除：
(0, 1)、(0, 3)、(1, 2)、(1, 3)、(1, 4)、(2, 3) 和 (3, 4)
它们的积分别是 2、4、6、8、10、12 和 20 。
其他下标对，例如 (0, 2) 和 (2, 4) 的乘积分别是 3 和 15 ，都无法被 2 整除。  
```

## 思考

首先想到的是动态规划，一个长度为 `n` 的数组结果与长度为 `n-1` 的关系是什么？

首先 `n-1` 时假设算好了一个结果 `result`，那么长度为 `n` 时，新产生的匹配是下标 `[0, n-1]` 与下标 `n` 数字的匹配关系，假设这些关系中有 `q` 个满足题设，则最终答案是 `result + q`。

这种想法适合 `(i, j)` 满足任意关系的题目，代码如下：

```js
function countPairs(nums: number[], k: number): number {
  if (nums.length < 2) {
    return 0
  }

  const dpCache: Record<number, number> = {}

  for (let i = 1; i < nums.length; i++) {
    switch (i) {
      case 1:
        if (nums[0] * nums[1] % k === 0) {
          dpCache[1] = 1    
        } else {
          dpCache[1] = 0
        }
        break
      default:
        // [0,i-1] 洗标范围内与 i 下标组合，看看有多少种可能
        let currentCount = 0
        for (let j = 0; j <= i - 1; j++) {
          if (nums[j] * nums[i] % k === 0) {
            currentCount++
          }
        }
        dpCache[i] = dpCache[i - 1] + currentCount
    }
  }

  return dpCache[nums.length - 1]
};
```

很可惜超时了，因为回头想想，虽然思路是 dp，但本质上是暴力解法，时间复杂度是 O(n²)。

为了 AC，必须采用更低复杂度的算法。

## 利用最大公约数解题

如果只循环一次数组，那么必须在循环到数组每一项的时候，就能立刻知道该项与其他哪几项的乘积符合 `nums[i] * nums[j]` 能被 k 整除，这样的话累加一下就能得到答案。

也就是说，拿到数字 `nums[i]` 与 `k`，我们要知道有哪些 `nums[j]` 是满足要求的。

当然，如果把所有剩余数字循环一遍来找满足条件的 `nums[j]`，那时间复杂度就还是 O(n²)，但不循环似乎无法继续思考了，这道题很容易在这里陷入僵局。

接下来就要发散思维了，先想这个问题：满足条件的 `nums[j]` 要满足 `nums[i] * nums[j] % k === 0`，那除了通过遍历把每一项 `nums[j]` 拿到真正的算一遍之外，还有什么更快的办法呢？

除了真的算一下之外，想想 `nums[j]` 还要具备什么特性？这个特性最好和倍数有关，因为如果我们计算所有数字倍数出现的个数，时间复杂度会比较低。

`nums[i]` 与 `k` 的最大公约数就满足这个条件，因为我们希望的是 `nums[j] * nums[i]` 是 `k` 的倍数，那么 `nums[j]` 最小的值就是 `k / nums[i]`，但这个除出来可能不是整数，那必须保证 k 除以的数字是一个整数，这个除数用 `nums[i]` 与 `k` 的最大公约数最划算。`nums[j]` 可以更大，只要是这个结果的倍数就行了，总结一下，`nums[j]` 要满足是 `k / gcd(nums[i], k)` 的倍数。

再重点解释下原因，我们假设 `nums[i] = 2`, `k=100`，此时是 k 比较大的情况，那么其最大公约数一定小于等于 `nums[i]`，因此 `k / 最大公约数 * nums[j]` 得到的数字一定大于 `k / nums[i] * nums[j]`，毕竟最大公约数比 `nums[i]` 小嘛，而 `k / nums[i] * nums[j]` 就是不考虑 `nums[j]` 是整数情况下让 k 可以整除 `nums[i] * nums[j]` 时，`nums[j]` 取的最小值的情况，因此 `nums[j]` 只要是 `k / 最大公约数` 的倍数就行了。

反之，如果 k 比 `nums[i]` 小，比如 `nums[i] = 100`, `k=2`，此时最大公约数是小于等于 k 的，但用一个比 k 还要大的 `nums[i]` 作为乘法的一边，乘出来的结果肯定大于 `k`，所以不用担心 `nums[i] * nums[j] < k` 的情况，所以 `nums[j]` 只要是 `k / 最大公约数` 的倍数就行了。

综上，无论如何 `nums[j]` 只要是 `k / 最大公约数` 的倍数就行了。

所以对于每一个 `nums[i]`，我们能快速计算出 `x = k / gcd(nums[i], k)`，接下来只要找到 nums 所有数字中，是 `x` 倍数的有多少累加起来就行了。这一步也不能鲁莽，因为数组长度非常大，性能更好的方案是：**先从1开始到最大值，计算出每个数字的倍数有几个，存在一个 map 表里，之后找倍数有几个直接从 map 表里获取就行了**。

比如有数字 `1 ~ 10`，我们要计算每个数字的倍数出现了几次，大概是这么算的：

- 1,2,3... 数到 10，那么 1 的倍数有 10 个数字。
- 2,4,6,8,10 数 5 次，那么 2 的倍数有 5 个数字。
- 3,6,9 数 3 次，那么 3 的倍数有 3 个数字。

以此类推，我们发现一个规律，即对于长度为 n 的数组，要数的总次数为 `n + n/2 + n/3 + ... + 1`，这是一个调和数列，具体怎么证明的笔者已经忘了，但可以记住它的值趋向于欧拉常数 + ln(n+1)，这就是要数的次数，所以用这个方案，整体时间复杂度是 O(nlnn)，比 O(n²) 小了很多。

所以我们只要 “暴力” 的从 1 开始到 nums 最大的数字，把所有数字的倍数都提前计算出来，最后的时间复杂度反而会更小，这是非常神奇的结论。为了避免计算多余的倍数关系，反而时间复杂度是 O(n²)，而暴力计算所有数字倍数的时间复杂度竟然是 O(nlnn)，这个可以背下来。

接下来就简单了，直接上代码。

用 js 实现 gcd（最大公约数）计算可以用辗转相除法：

```js
function gcd(left: number, right: number) {
    return right === 0 ? left : gcd(right ,left % right)
}
```

整体代码实现：

```js
function countPairs(nums: number[], k: number): number {
    // nums 最大的数字
    let max = 0
    nums.forEach(num => max = Math.max(num, max))

    // Map<数字x, 数字x 倍数在 nums 中出现的次数>
    const mutipleMap: Record<number, number> = {}

    // 先遍历一次 nums，将其倍数次自增
    nums.forEach(num => {
        if (mutipleMap[num] === undefined) {
            mutipleMap[num] = 1
        } else {
            mutipleMap[num]++
        }
    })

    // 按以下规律数倍数出现的次数，但忽略自身
    // 1,2,3...,max
    // 2,4,6...,max
    // 3,6,9...,max
    for (let i = 1; i <= max; i++) {
        for (let j = i * 2; j <= max; j+=i) {
            if (mutipleMap[i] === undefined) {
                mutipleMap[i] = 0
            }
            mutipleMap[i] += mutipleMap[j] ?? 0
        }
    }

    // 答案
    let result = 0

    // k / gcd(num, k) 的数组出现的次数累加
    nums.forEach(num => {
        const targetMutiple = k / gcd(num, k)
        result += mutipleMap[targetMutiple] ?? 0
    })

    // 排除自己乘以自己满足条件的情况
    nums.forEach(num => {
        if (num * num % k === 0) { result-- }
    })
    
    return result / 2
};
```

有几个注意要点。

第一个是 `for (let j = i * 2`，之所以要乘以 2，是因为在前面遍历 nums 时，自己的倍数已经被算过一次，比如 3,6,9 的 3 已经被初始化算过一次，所以从 3*2=6 开始就行了。

第二个是 `mutipleMap[i] += mutipleMap[j]`，比如 i=3，j=9 时，因为 9 是 3 的倍数，所以此时 3 的倍数可以继承 9 的倍数的数量，而数字是不断变大的，所以不会重复。

第三个是 `if (num * num % k === 0) { result-- }`，因为题目要求 `0 <= i < j <= n - 1`，但我们计算倍数时，比如 9 是 3 的倍数，但 9 可以通过 3 * 3 得到，这种不合规的数据要过滤掉。

第四个是 `return result / 2`，因为在最后累加次数时，把每个数字与其他数字都判断了一遍，假设 `1, 3` 是合法的，那么 `3, 1` 也肯定是合法的，但因为 `i < j` 的要求，我们要把 `3, 1` 干掉，所有合法的结果都存在顺序颠倒的 case，所以除以 2.

## 总结

这道题很容易栽在动态规划超时的坑上面，要解决此题需要跨越两座大山：

1. 想到最大公约数与另一个数字之间的关系。
2. 意识到暴力计算倍数的时间复杂度是 O(nlnn)。

最后，本题还隐含了 `n + n/2 + n/3 + ... + 1` 为什么极限是 O(nlnn) 的知识，背后有一个 [调和数列](https://zh.wikipedia.org/zh-cn/%E8%B0%83%E5%92%8C%E7%BA%A7%E6%95%B0) 的大知识背景，感兴趣的同学可以深入了解。

> 讨论地址是：[精读《算法 - 统计可以被 K 整除的下标对数目》· Issue #495 · dt-fe/weekly](https://github.com/dt-fe/weekly/issues/495)

**如果你想参与讨论，请 [点击这里](https://github.com/dt-fe/weekly)，每周都有新的主题，周末或周一发布。前端精读 - 帮你筛选靠谱的内容。**

> 版权声明：自由转载-非商用-非衍生-保持署名（[创意共享 3.0 许可证](https://creativecommons.org/licenses/by-nc-nd/3.0/deed.zh)）